class SolutionZsh {
    public int numTrees(int n) {
        int[] result = new int[n + 1];
        result[0] = 1;
        result[1] = 1;
        for (int i = 2; i < result.length; i++) {
            int value = 0;
            int childNodeNumber = i - 1;
            for (int j = 0; j < i; j++) {
                value += result[j] * result[childNodeNumber - j];
            }
            result[i] = value;
        }
        return result[n];
    }
}